#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*
 * 2022/9/15	10:16	qing
 */

/*
 * 论程序底层优化的一些方法与技巧
 */

unsigned long long get_clock()
{
	unsigned long long ret;

	/* RDTSC : Read time stamp counter. */
	__asm__ __volatile__ ("rdtsc\n\t":"=A"(ret):);

	return ret;
}

/* 最初版 */
int get_max(int *a, int l)
{
	int mx = 0, i = 0;

	for (i = 0; i < l; i++) {
		if (a[i] > mx)
			mx = a[i];
	}

	return mx;
}

/*
 * 第一次优化
 *
 * a[i] 被提及两次，重复计算地址开销不可忽略。
 *
 * 以下解决重复寻址的问题，属于逻辑层面的优化 
 */
int get_max1(int *a, int l)
{
	int mx = 0, *ed = a + l;

	while (a != ed) {
		if (*a > mx)
			mx = *a;
		a++;
	}

	return mx;
}

/*
 * 第二次优化
 * 
 * 将原来单线的求最大值进程分为八路，最后再来汇总总的最大值。
 */
int get_max2(int *a, int l)
{
	assert (l % 8 == 0);

	#define D(x)	mx##x = 0
	
	int D(0), D(1), D(2), D(3), D(4), D(5), D(6), D(7);
	int *ed = a + l;

	#define CMP(x) if (*(a + x) > mx##x) \
						mx##x = *(a + x);

	while (a != ed) {
		CMP(0); CMP(1); CMP(2); CMP(3); 
		CMP(4); CMP(5); CMP(6); CMP(7); 

		a += 8;
	}

	#define CC(x1, x2) if (mx##x1 > mx##x2)	\
							mx##x2 = mx##x1;
	CC(1, 0); CC(3, 2); CC(5, 4); CC(7, 6); 
	CC(2, 0); CC(6, 4); CC(4, 0); 

	return mx0;
}

/*
 * 第三次优化
 *
 * 直接朴素地将原始意图使用汇编语言实现一遍
 */
int get_max3(int *a, int l)
{
    int ret;

    __asm__  __volatile__ (
        "movl $0, %%eax\n\t"
        ".p2align 4,,15\n\t"
        "LP1:\n\t"
        "cmpl -4(%1,%2,4), %%eax\n\t"
        "jge ED\n\t"
        "movl -4(%1,%2,4), %%eax\n"
        "ED:\n\t"
        //"loop LP1\n\t"
        "decl %2\n\t"
        "jnz LP1\n\t"
        :"=m"(ret)
        :"r"(a),"c"(l)
        :"%eax"
        );

    return ret;
}

/*
 * 第四次优化
 *
 * 降低程序上下文依赖性！
 *
 * 在前面的第二次优化中，这种方法起到了非常好的效果，那就在汇编语言再来一次
 */
int get_max4(int *a, int l)
{
    assert(l % 2 == 0);

    int ret = 0;

    __asm__ __volatile__(
        "movl $0, %%eax\n\t"
        "movl $0, %%edx\n\t"
        ".p2align 4,,15\n"
        "LP2:\n\t"
        "cmpl (%1), %%eax\n\t"
        "jge ED2\n\t"
        "movl (%1), %%eax\n"
        "ED2:\n\t"
        "cmpl 4(%1), %%edx\n\t"
        "jge ED3\n\t"
        "movl 4(%1), %%edx\n"
        "ED3:\n\t"
        "addl $8, %1\n\t"
        "subl $2, %2\n\t"
        "jnz LP2\n\t"
        "cmpl %%edx, %%eax\n\t"
        "cmovll %%eax, %%eax\n\t"
        "movl %%eax, %0\n\t"
        :"=m"(ret)
        :"r"(a),"r"(l)
        :"%eax","%edx"
    );

    return ret;
}

/*
 * 第五次优化
 *
 * 单指令多数据(SIMD)
 *
 * 考虑程序各处似乎都无利可图了，优化再次陷入僵局。想要再取得优化，必须再打开思维才行。
 *
 * 用SSE指令集来处理这个问题的方式有些间接，大体思路仍然是多路求值，不过这次的这四路局部最大值，
 * 打包保存在xmm0寄存器中。
 */
int get_max5(int *a, int l)
{
    assert(l % 4 == 0);
    //assert(sse2);
    int ret, tmp[4];

    __asm__ __volatile__(
        "xorps %%xmm0, %%xmm0\n"
        "LP3:\n\t"
        "movdqa %%xmm0, %%xmm1\n\t"
        "pcmpgtd (%1), %%xmm1\n\t"
        "andps %%xmm1, %%xmm0\n\t"
        "andnps (%1), %%xmm1\n\t"
        "orps %%xmm1, %%xmm0\n\t"
        "addl $16, %1\n\t"
        "subl $4, %2\n\t"
        "jnz LP3\n\t"
        "movdqu %%xmm0, (%3)\n\t"
        "movl (%3), %%eax\n\t"
        "cmpl 4(%3), %%eax\n\t"
        "cmovll 4(%3), %%eax\n\t"
        "cmpl 8(%3), %%eax\n\t"
        "cmovll 8(%3), %%eax\n\t"
        "cmpl 12(%3), %%eax\n\t"
        "cmovll 12(%3), %%eax\n\t"
        "movl %%eax, %0\n"
        :"=m"(ret)
        :"r"(a),"r"(l),"r"(tmp)
        :"%eax"
    );

    return ret;
}

/*
 * 第六次优化
 *
 * 程序的优化是无止境的。
 *
 * 使用SSE4指令集，其中有一条pmaxsd指令，可直接取代前面的位运算步骤。
 */
int get_max6(int *a, int l)
{
    assert(l % 4 == 0);
    //assert(sse4);

    int ret, tmp[4];

    __asm__ __volatile__(
        "\txorps %%xmm0, %%xmm0\n"
        "LP4:\n\t"
        "pmaxsd (%1), %%xmm0\n\t"
        "addl $16, %1\n\t"
        "subl $4, %2\n\t"
        "jnz LP4\n\t"
        "movdqu %%xmm0, (%3)\n\t"
        "movl (%3), %%eax\n\t"
        "cmpl 4(%3), %%eax\n\t"
        "cmovll 4(%3), %%eax\n\t"
        "cmpl 8(%3), %%eax\n\t"
        "cmovll 8(%3), %%eax\n\t"
        "cmpl 12(%3), %%eax\n\t"
        "cmovll 12(%3), %%eax\n\t"
        "movl %%eax, %0\n"
        :"=m"(ret)
        :"r"(a),"r"(l),"r"(tmp)
        :"%eax"
    );

    return ret;
}

int main()
{
	int ac[1000000] = {
		2620, 2646, 2672, 2699, 2726, 2753, 2781, 2808,
		15096, 15247, 15399, 15553, 15709, 15866, 16024, 16184,
		2837, 2865, 2894, 2923, 2952, 2981, 3011, 3041,
		3072, 3102, 3133, 3165, 3196, 3228, 3261, 3293,
		20756, 20963, 21173, 21385, 21598, 21814, 22033, 22253,
		3326, 3359, 3393, 3427, 3461, 3496, 3531, 3566,
		19167, 19359, 19553, 19748, 19946, 20145, 20347, 20550,
		3602, 3638, 3674, 3711, 3748, 3786, 3823, 3862,
		22475, 22700, 22927, 23156, 23388, 23622, 23858, 24097,
		3900, 3939, 3979, 4019, 4059, 4099, 4140, 4182,
		4224, 4266, 4308, 4352, 4395, 4439, 4483, 4528,
		12167, 12359, 12553, 19728, 19926, 20125, 20337, 20555,
		4574, 4619, 4665, 4712, 4759, 4807, 4855, 4903,
		4953, 5002, 5052, 5103, 5154, 5205, 5257, 5310,
		28538, 28823, 29112, 29403, 29697, 29994, 30294, 30597,
		5363, 5417, 5471, 5525, 5581, 5636, 5693, 5750,
		5807, 5865, 5924, 5983, 6043, 6104, 6165, 6226,
		26354, 26618, 26884, 27153, 27424, 27699, 27976, 28255,
		6289, 6351, 6415, 6479, 6544, 6609, 6675, 6742,
		6810, 6878, 6946, 7016, 7086, 7157, 7229, 7301,
		17701, 17878, 18057, 18237, 18420, 18604, 18790, 18978,
		7374, 7448, 7522, 7597, 7673, 7750, 7828, 7906,
		7985, 8065, 8145, 8227, 8309, 8392, 8476, 8561,
		13940, 14080, 14221, 14363, 14506, 14652, 14798, 14946,
		8647, 8733, 8820, 8909, 8998, 9088, 9178, 9270,
		9363, 9457, 9551, 9647, 9743, 9841, 9939, 10038,
		10139, 10240, 10343, 10446, 10550, 10656, 10763, 10870,
		10979, 11089, 11200, 11312, 11425, 11539, 11654, 11771,
		11889, 12008, 12128, 12249, 12371, 12495, 12620, 12746,
		12874, 13002, 13132, 13264, 13396, 13530, 13666, 13802,
		13940, 14080, 14221, 14363, 14506, 14652, 14798, 14946,
		15096, 15247, 15399, 15553, 15709, 15866, 16024, 16184,
		16346, 16510, 16675, 16842, 17010, 17180, 17352, 17526,
		17701, 17878, 18057, 18237, 18420, 18604, 18790, 18978,
		19167, 19359, 19553, 19748, 19946, 20145, 20347, 20550,
		20756, 20963, 21173, 21385, 21598, 21814, 22033, 22253,
		22475, 22700, 22927, 23156, 23388, 23622, 23858, 24097,
		24338, 24581, 24827, 25075, 25326, 25579, 25835, 26093,
		26354, 26618, 26884, 27153, 27424, 27699, 27976, 28255,
		28538, 28823, 29112, 29403, 29697, 29994, 30294, 30597,
		30903, 31212, 31524, 31839, 32157, 32479, 32804
	};
	int max = 0;
	unsigned long long cycle_new = 0, cycle_old = 0;
#if 0
	cycle_old = get_clock();
	max = get_max(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	cycle_old = get_clock();
	max = get_max1(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	cycle_old = get_clock();
	max = get_max2(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	cycle_old = get_clock();
	max = get_max3(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	cycle_old = get_clock();
	max = get_max4(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);
#endif
	cycle_old = get_clock();
	max = get_max5(ac, 1000000);
	cycle_new = get_clock();
	printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	//cycle_old = get_clock();
	//max = get_max6(ac, 1000000);
	//cycle_new = get_clock();
	//printf("max vlaue : %d, cycle = %lld\n", max, cycle_new - cycle_old);

	return 0;
}
